Chapter 4: Collections

Taxonomy

We have already encountered some collections in the previous chapter – arrays, tuples, dicts and sets.

This chapter examines what we can do with collections and how to best use them for maximum effectiveness. A collection may be indexable, associative or neither. This refers primarily to the way we access individual elements within the collection.

• Indexable: An indexable collection is like a shopping list – the only way to identify individual elements is by pointing out their position. If you want to refer to, say, 1 pint of milk, you refer to it as the fifth entry on my shopping list.
  • Elements of an indexable collection are accessed using the square bracket notation collection[index], e.g. shopping_list[5]. Unusually for most programming languages and in sharp contrast to other languages like Python, indices begin with 1, rather than 0.
  • An indexable collection is also only equal to a collection with the same elements if they are in the same order – thus [1, 3, 5, 7] == [3, 7, 1, 5] yields, as one would expect, false.

• Associative: These collections, on the other hand, resemble a page from a phone book instead (if any of you actually still remember what one of those things is!). You wouldn't say that your phone number is on page 217, left column, fifth from the bottom. Rather, you would have a key (your name), by reference to which someone can find your phone number (the value).
  • Associative arrays do follow the key-value pair form. They are, therefore, not accessed in the collection[index] form but rather in the collection[key] form.
  • An associative collection is fundamentally not indexable, therefore the order of entries does not matter: two associative collections will be equal as long as they contain the same key-value pairs, order regardless.

• Neither: Collections that are neither associative nor indexable are a somewhat complex case; sets are the only frequently used collection that is neither associative nor indexable.
  • They are also special because of the uniqueness constraint, that is, a set may contain each value once and only once. A set does not support the commonly used methods of access, but it does support many of the collection manipulation functions, such as push!() and pop!(). The latter, in case you were wondering, returns items in a random order, since the absence of an index means sets are not ordered; you could pop!() any value off a set.
  • Sets are not indexable, consequently two sets that contain the same elements will be considered equal, order regardless.

In addition, collections may be mutable or non-mutable, which references their ability to be changed. Put quite simply, a mutable collection is one where you can change particular values after creation, while in an immutable collection, you cannot do so.

The typical immutable collections are, of course, tuples – once you have assigned a value to a tuple, you cannot change that value (although you can assign some other tuple or indeed an entirely different value to the variable that holds the tuple).

Sets again represent a special case – they are what could be best described as pseudo-immutable – there is no way to access values in a way that could change them, since you normally access an element of a set by its value (which is sufficient in a set thanks to the uniqueness constraint).

Indexable Collections

Accessing

Elements of an indexable collection can be accessed using the square bracket notation, by their ordinal:

In Julia, a range of numbers is written as start:end or start:steps:end. You can use a range to access a range of elements:

A range always returns a collection, even if it has the length 1.

This is exemplified by the difference between prime_array[3], the call we made above, and prime_array[3:3], which returns:

Which is not the same as the single value 5 we returned before from prime_array[3]:

You can access the last element of an indexable collection using [end]:

Incidentally, end behaves like a number – so prime_array[end-1] returns the penultimate element of the collection.

Setting

If the indexable collection you are using is also mutable (e.g. an array), any of these methods will act as a pseudo-variable and will allow you to assign a value to it. Thus prime_array[end] = 12 would change the last element of prime_array to 12. You also aren't restricted to a single element: calling prime_array[2:4] = 0 would result in

And, of course, you can use an array or another indexable collection to replace values:

Unpacking

Indexable collections can unpack: that is, they can be assigned in a single line to as many distinct variables as they have elements.

This is a very convenient feature, and is much used in functional programming:

They don't even have to be the same length; we can associate as many variables as there are elements available:

But you cannot have more; the collection does not wrap around:

Unpacking can also be used to swap the contents of variables:

Modifying

push!, pop! and append!

push!, pop! and append! are popular functions used to work with collections.

Note: Functions with an exclamation mark ! indicate that they modify their argument. Consider the following:

push!

push! appends the value to the end of the collection.

pop!

pop! takes the last element of the list, returns it and removes it from the collection.

append!

append!, somewhat unusually, adds the elements of a collection to the end of another collection:

shift!

shift! and unshift! are the front equivalent of pop! and push!; they add or remove values from the front of a collection.

Similarly to pop!, shift! retrieves the first element of the collection and removes it from the collection (which shifts it):

unshift!

Similarly to push!, unshift! puts an element to the front of the collection:

Finding

There's a set of functions starting with find — such as find(), findfirst(), and findnext() — that you can use to get the index or indices of values within an indexable collection that match a specific value, or pass a test. These functions share three properties.

1. Their result is the index or indices of the value sought or tested for, with the n^th element's index being n, not n-1 as you might be used to from other languages (Since we start from 1).

2. You can use these functions in two principal forms: you can test for a value or you can test for a function, in which case the results will be the values for which the function returns true.

3. The find functions' way of telling you they haven't found anything is returning zero, since there is no element of index zero.

Let's try to find things within the following Array: primes_and_one = [1,2,3,5,7,11,13,17,19,23]

findfirst()

findfirst() finds the first occurrence of a value and returns its index (or zero):

As noted above, we can feed the find functions a function as well – it will return values for which the function would return a true value.

We have not really discussed functions, but the general idea should be familiar to you. A function of the form x -> x == 13 results in true of the value of x is 13 and false otherwise.

Let's try to see which prime number is the first to equal 13 (don't expect big surprises):

You might have noticed that unlike in the case where you were searching for a particular value, where you're searching by a function, the function comes first (findfirst(array, value) vs. findfirst(function, array))

This is a little idiosyncrasy, but has to do with the way Julia determines what to do based on what it is provided with. A lot more of this will be explored in a later Chapter. .

find()

find() returns an array of results, not just the first match.

Thus, let's use the isinteger function to see which of our primes are integers (yet again, the result should not come as a shock):

findnext()

findnext() returns results from a given index onwards.

Thus, if you want to know the index of the first odd number after index 3 in the list of primes, you would proceed as follows (using the function isodd, which, as you could guess, returns true for odd integers and false otherwise):

Wait, why 4? As you might remember, Julia is 1-indexed, not 0-indexed, and inclusive. Therefore, an index 'begins before' the number.

The number after the first index is the first number in the sequence and so on. As such, the number after the third item in a collection is the item next to (= following) the index 4, not 3.

You might also have noticed that when you use a function as an argument, you do not use the parentheses you would normally use to call a function. That is because function() means call this function while function is merely a reference to the function object itself.

Retrieving

So far, we've only been getting indices. How do we retrieve the actual elements? The answer is, of course, by using our magical [](square brackets) syntax. We'll also use this as a good opportunity to introduce a very useful function, isprime(), which returns true for primes and false otherwise:

Filtering

The filter() function works quite similar to find, except in this case returns only the elements that satisfy the condition (it is, effectively, a shorthand for the previous listing):

filter() can be used in-place, by using the ! after the name of the function (thereby changing the original variable).

Using filter!(), altering the actual array rather than returning a filtered copy. Note, however, that functions ending with ! modify the object, so, obviously immutable type they act on must be mutable – you would, therefore, not be able to filter!() a tuple, even though you would be able to filter() it.

Sorting

The sort() function sorts an array lexicographically, generally in an ascending order:

You can specify the sort criterion with a function using by – in this case, we will be using the absolute value function abs (remember not to use the parentheses symbolising function call, just the name of the function):

You can change the order of sorting using rev:

And, for the great joy of algorithm nerds, you can choose the sort algorithm using alg.

Here's a fun review of some sorting algorithms:

Julia currently supports three sorting algorithms (InsertionSort, QuickSort and MergeSort).

For mutable indexable collections, such as arrays, you can use sort!(), which sorts 'in place'.

You can also sort non-numeric elements, or indeed anything for which the isless() function is defined, which sorting uses internally:

Counting

count() tells you the number of instances in the collection that satisfy the criterion:

Testing

all() and any() implement two of the mathematical concepts known as quantifiers, with all() representing the universal quantifier "for all" (∀), while any() implements the existential quantifier "for any" (∃x).

These functions test whether all or any, respectively, of a collection satisfies a certain criterion, and return a single truth value.

Checking

To find out whether an array has a particular value among its elements, you can use in():

Somewhat strangely, in the in() syntax, the needle comes before the haystack, i.e. in(value, array), where value denotes the value you are looking for, just like other function references.

Particulars

Arrays

Arrays (the ones we used in our examples so far in this section) are mutable indexable collections. The type Array{T,N} indicates an N-dimensional array which elements' types are subtypes of T.

For instance, Array{Number, 2} is an 2-dimensional array. Its elements' types descend from Number (e.g.Int, Float64).

Access in multidimensional arrays

How do we access elements in a multidimensional array, a special form of indexable collection? Simple – in a multidimensional array, indexes go down each row, then from left to right. Therefore, this array

would be indexed as follows:

This is a little counterintuitive and different from the usual row/column notation, where you would use array[row][column].

In Julia, to retrieve a cell by row and column, use array[row, column]:

This generalizes for higher dimension arrays.

Tuples

A tuple is an ordered sequence of elements, like an array. A tuple is represented by parentheses and commas, rather than the square brackets used by arrays. The important difference between arrays and tuples is that tuples are immutable: you can't change the elements of a tuple, or the tuple itself, after creating it.

Tuples are generally used for small fixed-length collections — they're ubiquitous across Julia, for example as argument lists. Where a function returns multiple values, which, as we see, is pretty often the case, the result is a tuple.

A corollary of immutability is that none of the ! functions work on tuples - but at the same time, using functions such as push() is perfectly acceptable, since it returns a copy of the tuple with the added element, which does not alter the original tuple.

Associative Collections

An associative collection (typically Dictionaries) is a kind of non-indexed collection that stores (usually) pairs of values.

The indexable collections you have encountered correspond to real-life examples such as a shopping list or a sequential list of train stations. Associative collections, on the other hand, have a key and a value (for this reason, they are sometimes referred to as key-value pairs).

Julia, like many other programming languages, implements associative collections in an object called a dict (short for dictionary), which corresponds to 'maps', 'hash tables' or 'dictionaries' in other programming languages.

A dict, as we have seen, is usually created using the dict literal:

The key of a key-value pair is unique, meaning that while several keys might point at the same value (and a key might point at a collection as a value), you cannot have duplicate keys (in database terminology, you might have heard this referred to as a one-to-many relationship).

Creating

Other than the Dict() literal, there are three more ways to create a dict.

First, you can create a dict using the comprehension syntax for dicts. An example is

This creates a dict with the square root of every odd number from 1 to 15. In this case, i can be any iterable – while ranges are the most frequently used, there is no reason why.

The following would not be equally valid:

Note: Comprehension syntax is generally applicable to most collections:

Secondly, you can also create an empty dictionary. Dict() will construct an empty dictionary that permits any elements, while Dict{type1, type2}() will create an empty dictionary that permits any elements with keys of type1 and values of type2.

Finally, earlier versions of Julia used to support what is sometimes referred to as zip creation of a dict, namely entering two equal-length tuples, one for keys and one for values. This is now regarded as deprecated – it still works, but you should not use it. Instead, the correct syntax is Dict(zip(ks, vs)):

Accessing

Just like items in an indexable arrays are keyed by their index, items in a dict are identified by their key and retrieved using the square bracket syntax with the relevant key:

One drawback of the bracket syntax is that if there is no entry for the key provided, Julia will raise an error:

An alternative form of accessing a dictionary is using the get() function, which accepts a default value:

get()

This is particularly helpful for key-error handling; any not found entries all inherit this default response.

Unlike in some other programming languages, a default is not optional for Julia:

Modifying

get!()

Because dicts are mutable, get!() can create an access a value by its key and return this new value.

Its syntax is identical to the get() idea of a default value:

pop!()

pop!() drops the key-value array matching the key.

If the key does not exist, it returns an optional default value or throws an error:

Changing

To change a value, access it via the bracket syntax, then assign it the new value:

Checking

To check for the existence of a key without retrieving it, you can use haskey():

You can also check for the existence of a key-value pair in a dict using the in() function you might be familiar with from arrays using the associative array symbol =>:

Retrieving

To retrieve all keys of a dict, use keys().

This will retrieve an object of type KeyIterator, which does just what the name suggests - it iterates through the keys of an array. This will be useful later on when we want to iterate through the dictionary by keys:

You can retrieve values, predictably, by using the values() function:

Sorting

You may have noticed that dicts are unordered. Even a dict generated by reference to a range, such as the one seen above, will not be in any particular order:

This is because dicts are not indexable, therefore there is no ordering that would make inherent sense.

However, sometimes, we like dictionaries sorted. Disappointingly, sorting dicts is not as easy as sorting arrays: sort(statisticians) tells us that 'sort' has no method matching sort(::Dict{ASCIIString,ASCIIString}).

Therefore, you have to write your own sort function that first converts statisticians from a dict into an array of 2-element tuples. This is because the sort() function has no defined methods for dicts, but it can sort arrays, including tuples, where it sorts by the first element in the tuple.

We can emulate this functionality with sort(collect(statisticians)) which converts this Dict into another (typically an Array:

We then wrap this back up in a Dict:

Merging

The function merge() merges two or more dicts.

Its bang counterpart, merge!(), merges them in place, overwriting the first dict mentioned while leaving the second intact.

Non-Indexable & Non-Associative Collections

Sets are the primary collection of this type.

You might be familiar with the idea of sets from maths/set theory. A set is a non-indexable, non-associative and non-mutable collection that also has unique elements. No element may occur twice, so an element's value identifies it conclusively.

Creating

To create a set, use the Set() constructor function. You can create a set that accepts any data type

Or you can specify what sort of data types it would accept:

You can create and fill sets in one go by listing elements surrounded by curly braces {}, and if you surround the elements with square brackets [] instead of curly braces {} Julia will guess the type:

mersenne_primes_set = Set([3, 7, 31, 127])

Operating

Sets have some unique functions that accommodate certain problems well-known from set theory: the functions union(), intersect() and setdiff() each, respectively, implement the union, intersection and difference of sets. They are also immutable, so they cannot be changed; they can only generate new sets.

Let's see how we can use this to find some similarities between the cast of two blockbusters, The Lord of the Rings and The Matrix.

First, let's create two sets with some actors from each movie:

To find shared actors, we can use intersect():

To find actors who only starred in Lord of the Rings but not in The Matrix, we can use setdiff(), which shows all elements that are in the first Set but not the second:

Finally, we can see actors who played in either of the movies, by using union():

Collections & Types

Until now, we have generally created collections using literals, and with precious little regard to the types of information that go in them. While types will be discussed in quite a bit of detail later on, what we do know about types is that they are individual categories of data.

Julia operates what is called type inference: unless you tell it explicitly what type something is, it tries to figure it out best as it can. We see this in operation when we create a new collection. When a collection is created and Julia is not told that this is going to be a collection containing elements of only a particular kind or particular kinds of values, it makes an educated guess. The REPL tells us this much:

Upon creating the array, the REPL reports to us that it's an array consisting of six elements, all of type Int64 – a type of signed 64-bit integer (don't worry if that means quite little to you just yet, we will be discussing various integer types in Chapter [X]). It also, helpfully, reports to us that we've got a 1-dimensional array.

Type inference and dissimilar types

What, however, if I want to play it a little wild and mix it up? Consider the following array:

As you have guessed, Julia is at a loss as to what to do with this, since we've got a mix of integers, strings and a constant thrown in for good measure. Therefore, it tells us that it has inferred the type of the collection to be Any – a type that applies to all objects.

Type inference and empty collections

The other marginal case is that of the empty set. Julia has a dedicated type, None – a subtype of Any – that applies to the empty set:

Conclusion

In this chapter, we learned about the way Julia's handles collections, whether they are Indexable, Associative, or neither. An indexable array is referenced by its index value (starting from 1 in Julia), and provides a bunch of operations for changing, setting, modifying, finding, and even testing these collections. Associative arrays are based on the notion of key-value pairs, and are almost always dictionaries. They do not have an order, and rely on the notion of retrieving a value for a given key, not indices. Sets are neither indexable nor associative; they are a collection that deals exclusvily with unique values. In any case, they all share one important property – to act as 'envelopes' for multiple elements, each with their distinct type.